/**
 * LeetCode417：太平洋大西洋水流问题
 * 给定一个m*n的非负整数矩阵来表示一片大陆上各个单元格的高度
 * “太平洋”位于大陆的上边界和左边界，“大西洋”位于大陆的下边界和右边界
 * 水流只能按上下左右四个方向，只能从高流到低
 * 找出那些水流既能流到“大西洋”，又能流到“太平洋”的陆地单元的坐标
 */


/**
 * @description 新建两个矩阵，从四个边界对图进行深度优先遍历
 * @description 逆向找出能够流到边界的坐标，填充到矩阵中
 * @description 遍历两个矩阵，找到能流到两个大洋的坐标
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function (matrix){
    if (!matrix || !matrix[0]){
        return [];
    }
    const m = matrix.length;
    const n = matrix[0].length;
    const flow1 = Array.from({length:m}, () => new Array(n).fill(false));
    const flow2 = Array.from({length:m}, () => new Array(n).fill(false));

    const dfs = (r, c, flow) => {
        //水流到[r,c]位置后，将该位置的标记置为true
        //遍历上下左右四个方向的下一个坐标位置
        [[r-1,c],[r+1,c],[r,c-1],[r,c+1]].forEach((nr,nc) => {
            //保证下一个坐标还在矩阵中，未访问过该坐标，且“逆流而上”
            if (nr >= 0 && nr <= m && nc >= 0 && nc <= n && !flow[nr][nc] && matrix[nr][nc] >= matrix[r][c]){
                dfs(nr,nc,flow);
            }
        });
    };

    for (let i = 0; i < m - 1; i++) {
        //“太平洋”，从左边界出发，结果写在flow1中
        dfs(i,0,flow1);
        //“大西洋”，从右边界出发，结果写在flow2中
        dfs(i,n-1,flow2);
    }

    for (let i = 0; i < n - 1; i++) {
        //“太平洋”，从上边界出发，结果写在flow1中
        dfs(0,i,flow1);
        //“大西洋”，从下边界出发，结果写在flow1中
        dfs(m-1,i,flow1);
    }

    //将同时能流到两个大洋的坐标放入结果集
    const res = [];
    for (let r = 0; r < m; r+=1){
        for (let c = 0; c < n; c+=1){
            if (flow1[r][c] && flow2[r][c]){
                res.push([r,c])
            }
        }
    }
    return res;
};

//时间复杂度：O(m*n)
//空间复杂度：O(m*n)